package com.sheng.leetcode.year2022.month08.day08;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/08/08
 *
 * 761. 特殊的二进制序列
 *
 * 特殊的二进制序列是具有以下两个性质的二进制序列：
 *
 * 0 的数量与 1 的数量相等。
 * 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
 * 给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，
 * 然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
 * 在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
 *
 * 示例 1:
 * 输入: S = "11011000"
 * 输出: "11100100"
 * 解释:
 * 将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
 * 这是在进行若干次操作后按字典序排列最大的结果。
 * 说明:
 *
 * S 的长度不超过 50。
 * S 保证为一个满足上述定义的特殊 的二进制序列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/special-binary-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0761 {

    @Test
    public void test01() {
        String s = "11011000";
        System.out.println(new Solution().makeLargestSpecial(s));
    }
}
class Solution {
    public String makeLargestSpecial(String s) {
        //思路，以1...0这种格式对字符串s进行拆分，然后对子串进行排序，然后组合
        StringBuilder stringBuilder = new StringBuilder();
        List<String> list = new ArrayList<>();
        //start：要截取的子串的开头
        //end：要截取的子串的结尾；当前字符为1时，end加1；当前字符为0时，end减1，当end为0时，代表当前字符串满足0和1的数量相等
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end += s.charAt(i) == '1' ? 1 : -1;
            if (end == 0) {
                //当前子串一定是1开头，0结尾
                String str = s.substring(start + 1, i);
                //将子串排列组合后返回的值添加到集合中
                list.add("1" + makeLargestSpecial(str) + "0");
                //将start赋新的起点
                start = i + 1;
            }
        }
        //对集合进行排序
        Collections.sort(list);
        //从后往前开始拼接
        for (int i = list.size() - 1; i >= 0; i--) {
            stringBuilder.append(list.get(i));
        }
        return stringBuilder.toString();
    }
}
